const vm = new Vue({
    el: 'main',
    data: {
        host: window.location.origin,
        board: null,
        errMsg: '',
    },
    created: function() {
    },
    mounted: function() {
        this.board = this.createEmptyGrids()
    },
    watch: {
    },
    methods: {
        createEmptyGrids: function () {
            let board = []
            for (let i = 0; i < 9; ++i) {
                let row = []
                for (let j = 0; j < 9; ++j) {
                    row.push(
                        {
                            id: 9 * i + j + 1,
                            i: i,
                            j: j,
                            val: '',
                        }
                    )
                }
                board.push(row)
            }
            return board
        },
        clear: function() {
            this.errMsg = ''
            this.board = this.createEmptyGrids()
        },
        sample: function() {
            let board1 = [
                [".",".",".","1",".",".","3",".","."],
                ["9","8",".",".",".","7",".","6","."],
                [".",".",".",".","5","3",".",".","7"],
                [".",".",".",".",".",".","8",".","1"],
                ["4",".","5",".",".","8","9",".","."],
                ["3",".",".",".","7",".",".",".","."],
                [".",".",".",".","2","1",".","8","."],
                [".",".",".","9",".",".","4",".","."],
                [".",".",".","3",".",".",".",".","."]
            ]
            let board2 = [
                ['5','3','.','.','7','.','.','.','.'],
                ['6','.','.','1','9','5','.','.','.'],
                ['.','9','8','.','.','.','.','6','.'],
                ['8','.','.','.','6','.','.','.','3'],
                ['4','.','.','8','.','3','.','.','1'],
                ['7','.','.','.','2','.','.','.','6'],
                ['.','6','.','.','.','.','2','8','.'],
                ['.','.','.','4','1','9','.','.','5'],
                ['.','.','.','.','8','.','.','7','9'],
            ]
            this.clear()
            let r = Math.random()
            let b
            if (r > 0.5) {
                b = board2
            } else {
                b = board1
            }
            for (let i = 0; i < 9; ++i) {
                for (let j = 0; j < 9; ++j) {
                    if (b[i][j] !== '.') {
                        this.board[i][j].val = b[i][j]
                    }
                }
            }
        },
        solve: function() {
            this.errMsg = ''
            this.board = this.solveSudoku(this.board)
        },
        solveSudoku: function(board) {
            let copyBoard = []
            board.forEach(row => {
                let cols = []
                row.forEach(col => {
                    cols.push(col)
                })
                copyBoard.push(cols)
            })
            //先检查一次整个board是否有效，防止初始状态时同行同列同九宫格被填入重复的数字
            let validState = true
            tag:
            for (let i = 0; i < 9; ++i) {
                for (let j = 0; j < 9; ++j) {
                    if (copyBoard[i][j].val !== '' && !this.valid(copyBoard, i, j)) {
                        validState = false
                        break tag
                    }
                }
            }
            if (!validState) {
                this.errMsg = '初始状态有误'
                return copyBoard;
            }
            //逐行扫描找到第一个''，以开始进行递归回溯查找
            let nextR = -1
            let nextC = -1
            tag:
            for (let i = 0; i < 9; ++i) {
                for (let j = 0; j < 9; ++j) {
                    if (copyBoard[i][j].val === '') {
                        nextR = i
                        nextC = j
                        break tag
                    }
                }
            }
            //初始位置找到，开始逐个数字尝试
            for (let x = '1'; x <= '9'; ++x) {
                copyBoard[nextR][nextC].val = x + '';
                let valid = this.backtrack(copyBoard, nextR, nextC);
                if (valid) {
                    return copyBoard;
                }
            }
            this.errMsg = '解题失败'
            return copyBoard;
        },
        /**
         * BFS+回溯算法，在每个位置上尽力尝试
         */
        backtrack: function(board, r, c) {
            if (!this.valid(board, r, c)) {
                //r行c列的数字存在重复，无效
                return false
            }
            //有效，则在r行开始逐行扫描找出下一个''，以继续搜索
            let nextR = -1
            let nextC = -1
            tag:
                for (let i = r; i < 9; ++i) {
                    for (let j = 0; j < 9; ++j) {
                        if (board[i][j].val === '') {
                            nextR = i
                            nextC = j
                            break tag
                        }
                    }
                }
            if (nextR === -1) {
                //没有找到''，说明整个board的搜索已经完成，且得到一个有效的数独结果
                return true
            }
            //存在下一个''
            for (let x = '1'; x <= '9'; ++x) {
                //用1～9对该位置进行尝试
                board[nextR][nextC].val = x + '';
                let valid = this.backtrack(board, nextR, nextC)
                if (valid) {
                    //如果递归结果是有效的，说明完成搜索，且得到一个有效的数独结果
                    return true
                }
            }
            //r行c列位置已经对1～9进行尝试，但均以失败告终，说明是前面某个位置的数字填写是不正确的，回溯，重新变成''，并回到上一层状态
            board[nextR][nextC].val = ''
            return false;
        },
        /**
         * 判断board中，r行c列的数字是否有效，按照数独规则就是r行、c列以及r行c列所在的小九宫格数字不会重复
         */
        valid: function(board, r, c) {
            let number = board[r][c].val + ''
            //检查一列中是否有重复
            for (let i = 0; i < 9; ++i) {
                if (i !== r && number === board[i][c].val) {
                    return false
                }
            }
            //检查一行中是否有重复
            for (let j = 0; j < 9; ++j) {
                if (j !== c && number === board[r][j].val) {
                    return false
                }
            }
            //检查r、c所在九宫格中是否有重复
            let r_ = Math.floor(r / 3) * 3
            let c_ = Math.floor(c / 3) * 3
            for (let i = r_; i < r_ + 3; ++i) {
                for (let j = c_; j < c_ + 3; ++j) {
                    if (i !== r && j !== c && number === board[i][j].val) {
                        return false
                    }
                }
            }
            return true
        },
    },
})
